#include <stdio.h>
#include <stdlib.h>
#include <stack>
using std::stack;
#include "BinarySearchTree.h"

BinarySearchTree* BinarySearchTree::m_instance = 0;

BinarySearchTree* BinarySearchTree::Instance()
{
	if (!m_instance) {
		m_instance = new BinarySearchTree();
	}

	return m_instance;
}

node* BinarySearchTree::Search(node* root, int key)
{
	if (!root) return 0;
	if (key == root->key) return root;
	else if (key < root->key) return Search(root->lchild, key);
	else return Search(root->rchild, key);		
}

node* BinarySearchTree::ModifiedSearch(node* root, int key)
{
	if (!root) return 0;
	if (key == root->key) return 0;
	else if (key < root->key) {
		if (!root->lchild) return root;
		else return ModifiedSearch(root->lchild, key);
	} else {
		if (!root->rchild) return root;
        else return ModifiedSearch(root->rchild, key);	
	}
}

void BinarySearchTree::Insert(node* &root, int key)
{
	if (!root) {
		root = (node*)malloc(sizeof(node));
		root->key = key;
		root->lchild = root->rchild = 0;
	}

	node* tmp = ModifiedSearch(root, key);
	if (tmp) {
		node* ptr = (node*)malloc(sizeof(node));
		ptr->key = key;
		ptr->lchild = ptr->rchild = 0;
		if (key < tmp->key) tmp->lchild = ptr;
		else tmp->rchild = ptr;				
	}				
}

void BinarySearchTree::CreateTree(node* &root, int n)
{
	for(int i=0; i<n; ++i) {
		int key = rand() % n*10;
		Insert(root, key);	
	}					
}

int BinarySearchTree::Depth(node* root)
{
	if (!root) return 0;
	int m = 1 + Depth(root->lchild);
	int n = 1 + Depth(root->rchild);
	if (m > n) return m;
	else return n;		
}

void BinarySearchTree::InOrder(node* ptr)
{
	if (ptr) {
		InOrder(ptr->lchild);
		printf("%d ", ptr->key);
		InOrder(ptr->rchild);	
	}					
}

void BinarySearchTree::PreOrder(node* ptr)
{
	if (ptr) {
		printf("%d ", ptr->key);
		PreOrder(ptr->lchild);
		PreOrder(ptr->rchild);	
	}					
}

void BinarySearchTree::PostOrder(node* ptr)
{
	if (ptr) {
		PostOrder(ptr->lchild);
		PostOrder(ptr->rchild);	
		printf("%d ", ptr->key);
	}	
}

void BinarySearchTree::IterPreOrder(node* root)
{
	stack<node*> s;
	node* ptr = root;
	while(true) {
		for(ptr; ptr; ptr=ptr->lchild) {
			printf("%d ", ptr->key);
			s.push(ptr);		
		}	

		if (s.empty()) break;
		ptr = s.top();
		s.pop();
		ptr = ptr->rchild;					
	}		
}

void BinarySearchTree::IterInOrder(node* root)
{
	stack<node*> s;
	node* ptr = root;
	while(true) {
		for(ptr; ptr; ptr=ptr->lchild) {
			s.push(ptr);		
		}	

		if (s.empty()) break;
		ptr = s.top();
		printf("%d ", ptr->key);
		s.pop();
		ptr = ptr->rchild;					
	}		
}

bool BinarySearchTree::IsBalanced(node* ptr, int& depth)
{
	if (!ptr) {
		depth = 0;
		return true;			
	}			
	int left, right;
	if (IsBalanced(ptr->lchild, left)
		&& IsBalanced(ptr->rchild, right)) {
		int diff = abs(left-right);
		if (diff <= 1) {
			depth = 1 + (left > right ? left : right);	
			return true;
		}		
	}

	return false;		
}
